package leetcode.dp;

public class dp01 {
    public static void main(String[] args) {
        int[] weights = {2,2,6,5,4};
        int[] value = {6,3,5,4,6};
        System.out.println(process(weights,value,10,0,0,0));
    }
    public static int process(int[] weights,int[] value,int num,int curWeight,int curValue,int curNum){

        if (curNum >=weights.length || curWeight + weights[curNum] > num){
            return curValue;
        }
        //要当前数
      int p1 =  process(weights, value, num, curWeight+weights[curNum], curValue+value[curNum], curNum+1);
        //不要当前数
      int p2 = process(weights, value, num, curWeight, curValue, curNum+1);

        return Math.max(p1,p2);
    }
    //改动态规划
    public static int process2(int[] weights,int[] value,int num){
        int[][] dp =new int[weights.length+1][num];
        for (int i = 0; i < weights.length; i++) {
            if (weights[i]<num)
            dp[0][weights[i]] = value[i];
        }
        for (int i = 1; i < weights.length ; i++) {
            for (int j = weights[i]; j <= num; j++) {
                dp[i][j] = Math.max(dp[i][j-weights[i]]+value[i],dp[i-1][j]);
            }
        }
        return 0;
    }

}
